#include <stdio.h>
#include <stdlib.h>
#include "/usr/local/lib/libgmp.a"
#include "/usr/local/lib/libgmp.la"

/* Function Prototypes */
mpz_t fib(mpz_t n);
/*int isFib(int n);*/
void storeFib(mpz_t n);

/* Global Variables */
mpz_t MAX, count, *array;
mpz_init(MAX);
mpz_init(count);
mpz_set_ui(MAX,1024);
mpz_set_ui(count,0);

int main(int argc, char **argv) {
    /*int T = 1000000000, ctr = 0;*/
    /*scanf ("%d", &T);*/
    /*int arr[T];*/
    /*for (ctr = 0; ctr < T; ++ctr) {
        scanf ("%d", &arr[ctr]);
        arr[ctr] = ctr;
    }*/
    /*for (ctr = 0; ctr < T; ++ctr) {
        if (isFib(ctr)) {
            printf ("%d (Count: %d)\n", ctr, count);
        }
    }*/
    mpz_t f, c;
    mpz_init(f);
    mpz_init(c);
    mpz_set_ui(f,0);
    mpz_set_ui(c,0);
    while (f >= 0) {
        /*printf ("%d\n", f);*/
        /*++c;*/
        mpz_out_str(stdout,10,f);
        mpz_add_ui(c,c,1);
        mpz_set_ui(f,fib(c));
    }
    return 0;
}

mpz_t fib(mpz_t n) {
    if (n < count) { return (*(array + (n * sizeof(mpz_t)))); }
    else if (n == 0) { storeFib(0); return 0; }
    else if (n == 1 || n == 2) { storeFib(1); return 1; }
    else {
        mpz_t f;
        mpz_init(f);
        mpz_set_ui(f,(fib(n - 1) + fib(n - 2)));
        storeFib(f);
        return f;
    }
}

/*int isFib(int n) {
    int c;
    if (count > 0) {
        for (c = 0; c < count; ++c) {
            if (*(array + (c * sizeof(int))) == n) { return 1; }
        }
    }
    c = 0;
    int f = fib(0);
    while (f <= n) {
        if (f == n) { return 1; }
        ++c;
        f = fib(c);
    }
    return 0;
}*/

void storeFib(mpz_t n) {
    if (count == 0) {
        array = (mpz_t *) malloc(MAX * sizeof(mpz_t));
    }
    if (count == MAX) {
        mpz_t *newArray = (mpz_t *) malloc(MAX * 2 * sizeof(mpz_t));
        mpz_t ctr;
        for (ctr = 0; ctr < MAX; ++ctr) {
            *(newArray + (ctr * sizeof(mpz_t))) = *(array + (ctr * sizeof(mpz_t)));
        }
        free(array);
        array = newArray;
        MAX *= 2;
    }
    *(array + (count * sizeof(mpz_t))) = n;
    ++count;
}
